package java学习.leetcode.editor.cn;

import com.sun.source.tree.Tree;

import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.Stream;

/**
 * @author 刘世锦
 * 2022-12-28 16:49:39	 当前时间
 */
//给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。 
//
// 如果树中有不止一个众数，可以按 任意顺序 返回。 
//
// 假定 BST 满足如下定义： 
//
// 
// 结点左子树中所含节点的值 小于等于 当前节点的值 
// 结点右子树中所含节点的值 大于等于 当前节点的值 
// 左子树和右子树都是二叉搜索树 
// 
//
// 
//
// 示例 1： 
//
// 
//输入：root = [1,null,2,2]
//输出：[2]
// 
//
// 示例 2： 
//
// 
//输入：root = [0]
//输出：[0]
// 
//
// 
//
// 提示： 
//
// 
// 树中节点的数目在范围 [1, 104] 内 
// -105 <= Node.val <= 105 
// 
//
// 
//
// 进阶：你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内） 
// Related Topics 树 深度优先搜索 二叉搜索树 二叉树 
// 👍 564 👎 0

public class 二叉搜索树中的众数{
	public static void main(String[] args) {
		Solution solution = new 二叉搜索树中的众数().new Solution();
		ArrayList<String> man = new ArrayList<>();
		man.add("周星驰");
		man.add("周润发");
		man.add("周润发");
		man.add("成龙");
		man.add("李连杰");
		man.add("周瑜");
		ArrayList<String> woman = new ArrayList<>();
		woman.add("张曼玉");
		woman.add("林青霞");
		woman.add("柳岩");
		woman.add("王祖贤");
		woman.add("林志玲");

		Stream<String> stream = man.stream().filter(s -> s.startsWith("周")).distinct();
		stream.forEach(System.out::println);
		System.out.println("=======");
		Stream<String> stringStream = woman.stream().limit(4).filter(s -> s.length() == 3);
		stringStream.forEach(System.out::println);
//		Stream<String> concat = Stream.concat(stringStream, stream);
//		List<String> collect = concat.collect(Collectors.toList());
//		System.out.println(collect);
		List<Integer> integers2 = List.of(124, 2, 15, 12, 51, -5, 5);
		// 返回其中一个元素
		Optional<Integer> any = integers2.stream().findAny();
		System.out.println(any);


	}


//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
	/** 复习  @author 刘世锦
	 *  @date  2023/2/9 17:38
	 */
	Map<Integer,Integer> map = new HashMap<>();
//	int[] map
	public int[] findMode(TreeNode root) {
		Stack<TreeNode> stack = new Stack<>();
		while (!stack.isEmpty()||root!=null){

			while (root!=null){
				stack.push(root);
				root = root.left;
			}
			TreeNode node = stack.pop();

			map.put(node.val,map.getOrDefault(node.val,0)+1);

			root = node.right;

		}
		// map 排序 by value 逆序
		List<Map.Entry<Integer, Integer>> entryList = map.entrySet().stream().sorted((a, b) -> {
			return b.getValue() - a.getValue(); }).collect(Collectors.toList());
		ArrayList<Integer> list = new ArrayList<>();
		for (int i = 0; i < entryList.size(); i++) {
			if (entryList.get(i).getValue()==entryList.get(0).getValue()){
				list.add(entryList.get(i).getKey());
			}
		}
//		list转数组
		return list.stream().mapToInt(Integer::intValue).toArray();
	}


	// 复习end




	/**
	 * 不使用额外数组。
	 * max：出现次数相同最多的节点个数
	 * count：本次节点出现的次数
	 * pre 上一个节点
	 *
	 * 因为 二叉搜索树是有序的。故
	 */
	public int[] findMode1(TreeNode root) {
		if(root==null){
			return new int[0];
		}
		Stack<TreeNode> stack = new Stack<>();
		ArrayList<Integer> list = new ArrayList<>();
		int max = 0,count = 0;
		TreeNode pre = null;
		while (!stack.isEmpty()||root!=null){
			while (root!=null){
				stack.push(root);
				root = root.left;
			}
			TreeNode node = stack.pop();
			if (pre==null||pre.val!=node.val){
				count = 1;
			}else if (pre!=null&&pre.val==node.val){
				count++;
			}
			if (count>max){
				max = count;
				list.clear();
				list.add(node.val);
			} else if (count==max){
				list.add(node.val);
			}
			pre = node;
			root = node.right;
		}
		HashMap<Integer, Integer> map = new HashMap<>();
		for (int i = 0; i < list.size(); i++) {
			map.put(list.get(i),map.getOrDefault(list.get(i),0)+1);
			max = Math.max(max,map.get(list.get(i)));
		}
		return list.stream().mapToInt(Integer::intValue).toArray();
	}
	/**
	 * 0  1 2  3  4  5
	 * 0 1 12 12 48 49
	 *
	 * dp[0] = max
	 * dp[1] = 1
	 * dp[2] = 1,12 1
	 * dp[3] = 1,36 1
	 * dp[4] = 1,1 1
	 *
	 * 1 2 3 4 6
	 **/
	public int[] findMode2(TreeNode root) {
		if(root==null){
			return new int[0];
		}
		Stack<TreeNode> stack = new Stack<>();
		ArrayList<Integer> list = new ArrayList<>();
		while (!stack.isEmpty()||root!=null){
			while (root!=null){
				stack.push(root);
				root = root.left;
			}
			TreeNode node = stack.pop();
			list.add(node.val);
			root = node.right;
		}
		int max = 0;
		HashMap<Integer, Integer> map = new HashMap<>();
		for (int i = 0; i < list.size(); i++) {
			map.put(list.get(i),map.getOrDefault(list.get(i),0)+1);
			max = Math.max(max,map.get(list.get(i)));
		}
		ArrayList<Integer> result = new ArrayList<>();
		for(Map.Entry<Integer, Integer> item:map.entrySet()){
			if (item.getValue()==max){
				result.add(item.getKey());
			}
		}
//		int [] arr = new int[result.size()];
//		for (int i = 0; i < result.size(); i++) {
//			arr[i] = result.get(i);
//		}
		return result.stream().mapToInt(Integer::intValue).toArray();
	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
